package com.swak.algs;

import com.swak.algs.array.Prints;

/**
 * 归并排序: 使用非递归的模式，折腾： 步长。 步长按照 2的N（从0开始） 次幂来递增
 * 
 * 思路： <br>
 * 1. 排序<br>
 * 1.1 左边有序、右边有序<br>
 * 2. 合并<br>
 * 2.1 拷贝左边，拷贝右边
 * 
 * @author lifeng
 */
public class Code16 {

	static void process(int[] arr, int L, int R) {

	}

	/*
	 * 4, 2, 5, 1
	 * 0  1  2  3
	 */
	static void merge(int[] arr, int L, int LR, int R, int RR) {
		int[] a2 = new int[RR - L + 1];
		int i = L;
		int j = R;
		int N = 0;
		while (i <= LR && j <= RR) {
			if (arr[i] < arr[j]) {
				a2[N] = arr[i];
				i++;
				N++;
			} else if (arr[i] > arr[j]) {
				a2[N] = arr[j];
				j++;
				N++;
			}
		}
		while (i <= LR) {
			a2[N++] = arr[i++];
		}
		while (j <= RR) {
			a2[N++] = arr[j++];
		}
		for (int n = L; n <= R; n++) {
			arr[n] = a2[n - L];
		}
	}

	public static void main(String[] args) {
		int[] arr = { 4, 2, 5, 1 };
		process(arr, 0, arr.length - 1);
		Prints.print(arr);
	}
}